import { GridMap } from "./Grid";
import { AstarNode } from "./Node";

/**
 * A*寻路
 */
export class AStar {

	private static _instance: AStar;
	/**
	 * 单例
	 */
	public static get instance(): AStar {
		return this._instance = this._instance ? this._instance : new AStar();
	}
	/**
	 * 队列
	 */
	public queue: Array<Function> = [];
	/**
	 * 待考察表
	 */
	private _open: Array<AstarNode> = [];
	/**
	 * 已考察表
	 */
	private _closed: Array<AstarNode> = [];
	/**
	 * 终点Node
	 */
	private _endNode: AstarNode;
	/**
	 * 起点Node
	 */
	private _startNode: AstarNode;
	/**
	 * 保存路径
	 */
	private _path: Array<any>;
	/**
	 * 寻路算法
	 */
	private _heuristic: Function;
	/**
	 * 上下左右走的代价
	 */
	private _straightCost: number = 1.0;
	/**
	 * 斜着走的代价 
	 */
	private _diagCost: number = Math.SQRT2;


	public constructor() {
		//this._heuristic = this.manhattan;  
		//this._heuristic = this.euclidian;
		this._heuristic = this.diagonal;
	}

	/**
	 * 寻路
	 * @param startPos 起点
	 * @param endPos 终点
	 */
	public findPath(startPos: AstarNode|any, endPos: AstarNode|any): AstarNode[] {
		this._startNode = GridMap.instance.getNode(startPos.x, startPos.y);
		this._endNode = GridMap.instance.getNode(endPos.x, endPos.y);
		for (let index = 0; index < this._open.length; index++) {
			const element = this._open[index];
			element.isInOpen = false;
		}
		for (let index = 0; index < this._closed.length; index++) {
			const element = this._closed[index];
			element.isInClose = false;
		}
		this._open = [];
		this._closed = [];
		this._startNode.parent = null;
		this._startNode.g = 0;
		this._startNode.h = this._heuristic(this._startNode);
		this._startNode.f = this._startNode.g + this._startNode.h;

		return this.search();
	}

	/**
	 * 查找路径
	 */
	public search(): AstarNode[] {
		var node: AstarNode = this._startNode;
		while (node != this._endNode) {
			var startX = Math.max(0, node.x - 1);
			var endX = Math.min(GridMap.instance.numCols - 1, node.x + 1);
			var startY = Math.max(0, node.y - 1);
			var endY = Math.min(GridMap.instance.numRows - 1, node.y + 1);

			for (var i = startX; i <= endX; i++) {
				for (var j = startY; j <= endY; j++) {
					if (test == this._endNode) {
						test.parent = node;
						this.buildPath();
						return this._path;
					}
					var test: AstarNode = GridMap.instance.getNode(i, j);
					if (test == node || test.isInClose || !test.walkable || test.hasUnit) {
						continue;
					}
					var cost: number = this._straightCost;
					if (!((node.x == test.x) || (node.y == test.y))) {
						cost = this._diagCost;
					}
					var g = node.g + cost * test.costMultiplier;
					var h = this._heuristic(test);
					var f = g + h;
					if (test.isInOpen) {
						if (test.f > f) {
							test.f = f;
							test.g = g;
							test.h = h;
							test.parent = node;
						}
					}
					else {
						test.f = f;
						test.g = g;
						test.h = h;
						test.parent = node;
						this.add(this._open, test);
					}
				}
			}
			this._closed.push(node);
			node.isInClose = true;
			if (this._open.length == 0) {
				//console.log(this._closed, "AStar >> no path found");
				return [];
			}
			node = this._open[0];
			this.removeFirst(this._open);
		}
		this.buildPath();
		return this._path;
	}

	/**
	 * 获取路径
	 */
	private buildPath(): void {
		this._path = new Array();
		var node: AstarNode = this._endNode;
		this._path.push(node);
		while (node != this._startNode) {
			node = node.parent;
			this._path.unshift(node);
		}
	}
	/**
	 * 保存路径
	 */
	public get path() {
		return this._path;
	}

	private add(list: AstarNode[], node: AstarNode) {
		list.push(node);
		node.isInOpen = true;
		let index = list.length - 1;
		let fIndex = Math.floor((index - 1) / 2);
		while (index > 0 && list[index].f < list[fIndex].f)//子节点 < 父节点
		{
			this.swap(list, fIndex, index);//交换父子节点
			index = fIndex;//更新 index
		}
	}
	private removeFirst(list: AstarNode[]) {
		if (list.length == 1) {
			list[0].isInOpen = false;
			list.pop();
			//list.Clear();
			return;
		}
		list[0].isInOpen = false;
		this.swap(list, 0, list.length - 1);//交换首尾元素
		list.pop();//移除尾
		this.updateHeap(list, 0, list.length);//调整堆
	}
	private updateHeap(list: AstarNode[], i: number, len: number) {
		let temp = list[i];//记录待 调整 的值
		for (let k = 2 * i + 1; k < len; k = 2 * k + 1) {
			if (k + 1 < len)//存在右节点
			{
				if (list[k + 1].f < list[k].f)//右节点 < 左节点
				{
					k += 1;//选择较小的右节点
				}
			}
			//（左/右）子节点 < 父节点
			if (list[k].f < temp.f) {
				this.swap(list, k, i);//交换（要保证父节点一定小于子节点——小顶堆）
				i = k;//更新 i ，继续下一次循环
			}
			//子节点>父节点
			else {
				break;//跳出循环，此处不需要往深层次遍历的原因在于：在堆排序中是从最后一个非叶子节点开始倒着向前 UpdateHeap
			}
		}
	}
	private swap(list: AstarNode[], a: number, b: number) {
		let temp = list[a];
		list[a] = list[b];
		list[b] = temp;
	}
	/**
	 * 曼哈顿算法
	 * @param node 
	 */
	private manhattan(node: AstarNode) {
		return Math.abs(node.x - this._endNode.x) * this._straightCost + Math.abs(node.y + this._endNode.y) * this._straightCost;
	}

	/**
	 * 欧几里德算法
	 * @param node 
	 */
	private euclidian(node: AstarNode) {
		var dx = node.x - this._endNode.x;
		var dy = node.y - this._endNode.y;
		return Math.sqrt(dx * dx + dy * dy) * this._straightCost;
	}
	/**
	 * 对角线算法
	 * @param node 
	 */
	private diagonal(node: AstarNode) {
		var dx = Math.abs(node.x - this._endNode.x);
		var dy = Math.abs(node.y - this._endNode.y);
		var diag = Math.min(dx, dy);
		var straight = dx + dy;
		return this._diagCost * diag + this._straightCost * (straight - 2 * diag);
	}
	/**
	 * A*寻路心跳
	 * @param dt 
	 */
	public update(dt?) {
		let length = this.queue.length;
		if (length > 30) {
			length = 30;
		}
		for (let index = 0; index < length; index++) {
			let f = this.queue.shift();
			if (f) {
				f();
			}
		}
	}
}